import java.util.Arrays;

/**
 * Created by L.jp
 * Description:
 * User: 86189
 * Date: 2021-10-23
 * Time: 17:13
 */
/*
时间复杂度：O（n*logn),每一层都有n个元素，高度是logn
空间复杂度：0（n),每次递归需要额外创建一个数组，大小为n
 */
public class MergeSort {
    //合并两个有序数组2
    /*public static  int[] mergeArray(int[]arr1,int[]arr2){
        int s1=0;
        int e1=arr1.length-1;
        int s2=0;
        int e2=arr2.length-1;
        int[]tmp=new int[arr1.length+arr2.length];
        int k=0;
        while(s1<=e1 && s2<=e2){
            if(arr1[s1]<=arr2[s2]){
                tmp[k++]=arr1[s1++];
            }else{
                tmp[k++]=arr2[s2++];
            }
            //当其中一个数组遍历完时，另一个数组还有剩余元素，直接给tmp
            while(s1<=e1){
                tmp[k++]=arr1[s1++];
            }
            while(s2<=e2){
                tmp[k++]=arr2[s2++];
            }
        }
        return tmp;
    }*/

    //递归

    //分解
    public static void mergeSort(int[]arr, int left, int right){
        if(left>=right){
            return ;//递归结束条件
        }
        int mid=(left+right)/2;
        mergeSort(arr,left,mid);
        mergeSort(arr,mid+1,right);
        //分解到left和right相遇，说明一个段只剩一个元素，接下来要合并段了
        merge(arr,left,right,mid);//每次递归的段等到递归结束返回的时候都要合并
    }
    //合并
    public static void merge(int []arr,int left,int right,int mid){

        int s1=left;//第一段的开始，用于遍历左边段
        int e1=mid;//标记第一段结束
        int s2=mid+1;//第二段开始，用于遍历右边段
        int e2=right;//标记第二段结束
        int[]tmp=new int[right-left+1];
        int k=0;
        while(s1<=e1 && s2<=e2){
            if(arr[s1]<=arr[s2]){
                tmp[k++]=arr[s1++];

            }else{
                tmp[k++]=arr[s2++];
            }
            while(s1<=e1){
                tmp[k++]=arr[s1++];

            }
            while(s2<=e2){
                tmp[k++]=arr[s2++];
            }
            //此时数组元素全部在tmp中，因为我们要排序原数组，所以要把tmp数组赋值到arr数组中
            for(int i=0;i<k;i++){
                arr[i+left]=tmp[i];//当合并右边段的时候，左边段已经存在了arr数组中，所以要从右边段开始存储，让i+left,此时的left是右边段的开始
            }
        }
    }
    //非递归
    public static void mergeSortNor(int []arr,int gap){
        int []tmp=new int[arr.length];
        int s1=0;
        int e1=s1+gap-1;
        int s2=e1+1;
        int e2=s2+gap-1>= arr.length-1 ? arr.length -1 :s2+gap-1;
        int k=0;
        //保证有两段
        while(s2<arr.length){
            //比较第一段和第二段
            while(s1<=e1 && s2<=e2){
                if(arr[s1]<=arr[s2]){
                    tmp[k++]=arr[s1++];
                }else{
                    tmp[k++]=arr[s2++];
                }
            }
            while(s1<=e1){
                tmp[k++]=arr[s1++];
            }
            while(s2<=e2){
                tmp[k++]=arr[s2++];
            }
            //比较接下来的段
             s1=e2+1;
             e1=s1+gap-1;
             s2=e1+1;
             e2=s2+gap-1>= arr.length-1 ? arr.length-1 : s2+gap-1;
             //接着继续循环比较
        }
        //此时s2超过了数组长度，只有一段,有两种情况，一是一开始就只有一个元素，第二是归并完前面的段之后只剩s1是数组最后一个元素，没有e1
        while(s1< arr.length){//如果没有e1,则会报错，所以不能是e1
            tmp[k++]=arr[s1++];
        }

        //全部比较完之后，把tmp数组的元素复制到arr数组中
        for (int i = 0; i < k; i++) {
            arr[i]=tmp[i];

        }
    }
    public static void mergeNor(int[]arr){
        for (int gap = 1; gap <arr.length ; gap*=2) {
            mergeSortNor(arr,gap);

        }
    }
    public static void main(String[] args) {
        int []arr={-1,-3,9,0,13,5,56};
        //mergeSort(arr,0, arr.length-1);
        mergeNor(arr);
        System.out.println(Arrays.toString(arr));
    }

}
